<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN""http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Variable Length Codes</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REL="HOME"
TITLE="LIBIT Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Source Coding Tools"
HREF="source.html"><LINK
REL="PREVIOUS"
TITLE="Quantization"
HREF="quantization.html"><LINK
REL="NEXT"
TITLE="Channel Coding Tools"
HREF="channel.html"></HEAD
><BODY
CLASS="SECTION"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>LIBIT Documentation</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="quantization.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
>Chapter 4. Source Coding Tools</TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="channel.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECTION"
><H1
CLASS="SECTION"
><A
NAME="VLC"
>4.3. Variable Length Codes</A
></H1
><P
>In the following, the term Variable Length Code (VLC)
stands for a scalar variable length code over a finite alphabet. 
Although strictly speaking, arithmetic codes are 
variable length codes, arithmetic codes are not covered by this term. 
A variable length code is defined as a set of binary codewords.  
Such a code is a prefix code, i.e. a given codeword can not be 
the prefix of another.  </P
><P
>In the library, the typename for Variable Length Codes objects is vlc_t. 
The users should only manipulate pointers vlc_t *. 
The set of supported construction methods for Variable Length Codes is
given below. All these methods return an allocated vlc_t pointer 
that allows to handle the corresponding object. </P
><DIV
CLASS="TABLE"
><A
NAME="AEN686"
></A
><P
><B
>Table 4-2. Variable Length Codes construction methods</B
></P
><TABLE
BORDER="1"
FRAME="border"
RULES="all"
CLASS="CALSTABLE"
><COL><COL><COL><THEAD
><TR
><TH
>Method</TH
><TH
>Function name</TH
><TH
>Description</TH
></TR
></THEAD
><TBODY
><TR
><TD
>Fixed length Code</TD
><TD
>vlc_flc</TD
><TD
>A code with all the codewords of the same size (lexicographic)</TD
></TR
><TR
><TD
>Huffman</TD
><TD
>vlc_huffman</TD
><TD
>The optimal Variable Length Code</TD
></TR
><TR
><TD
>Hu-Tucker</TD
><TD
>vlc_hu_tucker</TD
><TD
>The optimal lexicographic Variable Length Code</TD
></TR
><TR
><TD
>Generic</TD
><TD
>vlc_read</TD
><TD
>Custom code entered by the user as a string</TD
></TR
></TBODY
></TABLE
></DIV
><P
>The variable length encoder takes an input vector of symbols and outputs a vector of bits. The symbols are represented by integers between 0 and N-1, where N is the number of symbols handled by the variable length code. The encoding is processed using the function <A
HREF="man.vlc-encode-concat.html"
>vlc_encode_concat()</A
>, which takes the input vector of integers (type ivec) and produces a bitstream represented by a byte vector (bvec). The decoder takes such a bitstream as an input and allows to recover the original vector. It is handled with function vlc_decode_concat. </P
><P
>Here is an example on how to define and use a variable length code:</P
><DIV
CLASS="EXAMPLE"
><A
NAME="VLC-EXAMPLE"
></A
><P
><B
>Example 4-10. VLC example</B
></P
><PRE
CLASS="PROGRAMLISTING"
>  /* The probability distribution function of the source        */
  vec pdf = vec_new_string( "0.5 0.3 0.1 0.1" );

  /* Create an Huffman code optimum for the source pdf          */
  vlc_t * vlc = vlc_huffman( pdf );

  /* Generate a sequence according to the given probability law */
  int N = 20;
  ivec S = source_memoryless( N, pdf );

  /* Encode and decode the sequence S with the Huffman Code     */
  bvec B = vlc_encode_concat( vlc, S );
  ivec D = vlc_decode_concat( vlc, B );

  /* Print the vectors S, B and D                               */
  it_printf( "S = $d\nB = $b\nD = $d\n", S, B, D );

  /* Print the mean description length of the code and the 
     observed average description length                        */
  printf( "Mdl             = %lf\n", vlc_mdl( vlc, pdf ) );
  printf( "Obs. av. length = %lf\n",
            bvec_length( B ) / (double) ivec_length( S ) );

  /* Delete the code and defines an user defined code such that 
     its Kraft sum not equal to 1 . Print the code.             */
  vlc_delete( vlc );
  vlc = vlc_read( "{0 11 101 1001}" );
  printf( "Kraft sum       = %lf\n", vlc_kraft_sum( vlc ) );
  printf( "Custom Code     = " );
  vlc_print( vlc );
  printf( "\n" );
  
  vlc_delete( vlc );
  ivec_delete( S );
  ivec_delete( D );
  bvec_delete( B );

  /*------------------------------------------------------------
     The program generate something like that:

  S = [0 2 0 1 0 1 2 3 1 0 0 0 0 0 2 0 0 1 3 2]
  B = [0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0]
  D = [0 2 0 1 0 1 2 3 1 0 0 0 0 0 2 0 0 1 3 2]
  Mdl             = 1.700000
  Obs. av. length = 1.800000
  Kraft sum       = 0.937500
  Custom Code     = {0 11 101 1001}                             */
  </PRE
></DIV
><P
>Note that the users should not handle directly vlc_t objects but rather the corresponding pointers. The memory allocated by these functions should be freed with the function <A
HREF="man.vlc-delete.html"
>vlc_delete()</A
>.  </P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="quantization.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="channel.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Quantization</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="source.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Channel Coding Tools</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>